import collections

from LeetTool import ListNode
from LeetTool import build_ListNode


class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        # 添加哨兵结点
        ans = ListNode(0)
        ans.next = head

        # 统计出现频数
        count = collections.Counter()
        node = head
        while node:
            count[node.val] += 1
            node = node.next

        # 移除重复结点
        node = ans
        while node.next:
            if count[node.next.val] > 1:
                node.next = node.next.next
            else:
                node = node.next

        return ans.next


if __name__ == "__main__":
    # [1,3]
    print(Solution().deleteDuplicatesUnsorted(build_ListNode([1, 2, 3, 2])))

    # []
    print(Solution().deleteDuplicatesUnsorted(build_ListNode([2, 1, 1, 2])))

    # [1,4]
    print(Solution().deleteDuplicatesUnsorted(build_ListNode([3, 2, 2, 1, 3, 2, 4])))
